#include <iostream>
#include <vector>

using namespace std;

//传递数组指针的坑；
//https://blog.csdn.net/qq_54554848/article/details/128738618
//初始化数组的坑；
//https://blog.csdn.net/qq_55621259/article/details/126373884

// 抖机灵操作
static void swap1(int arr[],int i,int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

class MergeSort {
public:
    void mergeSort(int arr[],int len) {
        if (arr == nullptr || len < 2) return;
        return mergeSort(arr,0,len-1);
    }
    void mergeSort(int arr[],int l,int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r-l) >>1);
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
    void merge(int arr[],int l,int m,int r){
        int* help = new int[r-l+1]{};
        int i = 0;
        int p1 =l;
        int p2 =m+1;
        while(p1<=m&&p2<=r){
            help[i++] = arr[p1] < arr[p2]? arr[p1++]:arr[p2++];
        }
        while(p1 <=m ){
            help[i++] = arr[p1++];
        }
        while(p2 <=r ){
            help[i++] = arr[p2++];
        }
        for (i = 0; i < r-l +1 ;++i) {
            arr[l+i] = help[i];
        }
        delete[] help;
    }
};